//给定一个包含大写字母和小写字母的字符串
// s ，返回 通过这些字母构造成的 最长的回文串 。 
//
// 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 
//
// 
//
// 示例 1: 
//
// 
//输入:s = "abccccdd"
//输出:7
//解释:
//我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
// 
//
// 示例 2: 
//
// 
//输入:s = "a"
//输出:1
// 
//
// 示例 3： 
//
// 
//输入:s = "aaaaaccc"
//输出:7 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 2000 
// s 只由小写 和/或 大写英文字母组成 
// 
//
// Related Topics 贪心 哈希表 字符串 👍 545 👎 0

//最长回文串
package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

class P409LongestPalindrome {
    public static void main(String[] args) {
        Solution solution = new P409LongestPalindrome().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestPalindrome(String s) {
            //return fun1WithArrayCount(s);
            return fun2WithSet(s);
        }

        /**
         * set统计字符出现次数
         * 存在set中的元素是出现奇数次的元素
         */
        private int fun2WithSet(String s) {
            int res = 0;
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (!set.remove(c)) {
                    set.add(c);
                }
            }
            return set.size() == 0 ? s.length() : s.length() - set.size() + 1;
        }

        /**
         * 数组计数
         */
        private int fun1WithArrayCount(String s) {
            int result = 0;
            int[] counts = new int[128];
            for (int i = 0; i < s.length(); i++) {
                counts[s.charAt(i) - 'A']++;
            }
            boolean flag = false;
            for (int count : counts) {
                if (count % 2 == 1) {
                    result = result + (count - 1);
                    flag = true;
                } else {
                    result = result + count;
                }
            }
            return flag ? result + 1 : result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}